|
In computer science, linear search or sequential search is a method for finding a particular value in a list that checks each element in sequence until the desired element is found or the list is exhausted.〔 The list need not be ordered. Linear search is the simplest search algorithm; it is a special case of brute-force search. Its worst case cost is proportional to the number of elements in the list. Its expected cost is also proportional to the number of elements if all elements are searched equally. If the list has more than a few elements and is searched often, then more complicated search methods such as binary search or hashing may be appropriate. Those methods have faster search times but require additional resources to attain that speed. ==Analysis== For a list with ''n'' items, the best case is when the value is equal to the first element of the list, in which case only one comparison is needed. The worst case is when the value is not in the list (or occurs only once at the end of the list), in which case ''n'' comparisons are needed. If the value being sought occurs ''k'' times in the list, and all orderings of the list are equally likely, the expected number of comparisons is : For example, if the value being sought occurs once in the list, and all orderings of the list are equally likely, the expected number of comparisons is . However, if it is ''known'' that it occurs once, then at most ''n'' - 1 comparisons are needed, and the expected number of comparisons is : (for example, for ''n'' = 2 this is 1, corresponding to a single if-then-else construct). Either way, asymptotically the worst-case cost and the expected cost of linear search are both O(''n''). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「linear search」の詳細全文を読む スポンサード リンク
|